package day20210630;

import treenode.SimpleTreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 501. 二叉搜索树中的众数
 *
 * @author lizy
 * @date 2021/06/30
 */
public class Solution3 {

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.left = new SimpleTreeNode(2);
        simpleTreeNode.left.left = new SimpleTreeNode(1);
        simpleTreeNode.left.left.left = new SimpleTreeNode(1);
        System.out.println(Arrays.toString(solution.findMode(simpleTreeNode)));
    }

    int count = 0;  //记当前个数
    int max = 1;    //记最大值
    int pre_value = 0;  //记前一个value
    List <Integer> list = new ArrayList();  //一个个添加 只能用list

    public int[] findMode(SimpleTreeNode root) {
        BST(root);
        int [] result = new int [list.size()];  //初始化数组
        for(int i = 0; i < list.size(); i++) {  //list转array
            result[i] = list.get(i);
        }
        return result;
    }

    public void BST(SimpleTreeNode root) {    //左根右；中序遍历；从小到大
        if(root == null) {
            return;
        }
        BST(root.left);

        if(root.val == pre_value) { //如果和前一个相同 count+1
            count++;
        }  else {       //不同； 刷新count=1；刷新pre_value
            pre_value = root.val;
            count = 1;
        }
        if(count == max){   //如果是最大个数
            list.add(root.val); //加入list里
        } else if (count > max) {   //如果超过最大个数
            list.clear();   //清空整个list
            list.add(root.val); //加入list里（新的max）
            max = count;    //刷新max
        }

        BST(root.right);
    }

}
